Package edu.claflin.finder.algo

Class BronKerbosch

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.BronKerbosch

All Implemented Interfaces:

Processable<Graph,Graph>

public class BronKerbosch
extends Algorithm

Bron-Kersboch Algorithm to find Maximal Cliques and Bicliques.

See Also:

• Wikipedia Summary
• Original Paper
• Pivoting Variant

Nested Class Summary

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	bipartite

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
BronKerbosch(ArgumentsBundle bundle)	Public constructor for initializing the Bron Kersbboch with default conditions.

Method Summary

Modifier and Type	Method	Description
private void	addEdgesInParititeSet(Graph graph, List<Node> list)	Adds edges to a Graph between all Nodes in a partite set.
private void	bronKerbosch(List<List<Node>> results, List<Node> clique, List<Node> candidates, List<Node> excluded)	Recursive helper method to do the above.
private List<Graph>	bronKerboschBiclique(Graph graph)	Finds all bicliques within a bipartite graph.
private List<Graph>	bronKerboschClique(Graph graph)	Given a graph, finds all complete subgraphs.
private List<Graph>	maximalBicliques(Graph graph)	Gets the Maximal Complete Bipartite Graphs from the input Graph using Bron-Kersboch.
private List<Graph>	maximalCliques(Graph graph)	Given a graph, finds all complete subgraphs, and then returns the largest one.
private List<Graph>	nameGraphs(List<Graph> graphs, String originalName, boolean bipartite)
ArrayList<Graph>	process(Graph graph)	Processes data.
private void	removeEdgesInPartiteSet(Graph graph, List<Node> list)	Removes edges in a Graph between all Nodes in a partite set.
String	toString()

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getMinNodeCount, getPartiteNumber, getWeightName, removePropertyChangeListener, setGraphSortOrder, setMinNodeCount, setPartiteNumber, setProgress, setWeightName, zeropad

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

bipartite

private boolean bipartite

Constructor Details

BronKerbosch

public BronKerbosch(ArgumentsBundle bundle)

Public constructor for initializing the Bron Kersbboch with default conditions.

Parameters:

bundle - the ArgumentsBundle containing the instantiation arguments.

Method Details

toString

public String toString()

Overrides:

toString in class Object

process

public ArrayList<Graph> process(Graph graph)

Processes data.
Finds the Maximal Cliques of a Graph or the Maximal Biclique of a Bipartite Graph if the bipartite argument is set to true.

Parameters:

graph - the Graph object to search through.

Returns:

the ArrayList of Graph objects holding all found subgraphs.

maximalCliques

private List<Graph> maximalCliques(Graph graph)

Given a graph, finds all complete subgraphs, and then returns the largest one.

Parameters:

graph - the graph

Returns:

the largest complete subgraph (clique)

maximalBicliques

private List<Graph> maximalBicliques(Graph graph)

Gets the Maximal Complete Bipartite Graphs from the input Graph using Bron-Kersboch.

Parameters:

graph - the input Graph

Returns:

the Maximal Complete Bipartite Graphs

bronKerboschClique

private List<Graph> bronKerboschClique(Graph graph)

Given a graph, finds all complete subgraphs.

Parameters:

graph - the graph

Returns:

a List of complete subgraphs, unordered

bronKerboschBiclique

private List<Graph> bronKerboschBiclique(Graph graph)

Finds all bicliques within a bipartite graph. This is done by adding edges between every nodes in a partite set in both partite sets, using the above algorithm, and then removing all the added edges from the results. THIS ONLY WORKS ON GRAPHS THAT ARE BIPARTITE!

Parameters:

graph - the bipartite graph

Returns:

array list of bicliques

bronKerbosch

private void bronKerbosch(List<List<Node>> results,
 List<Node> clique,
 List<Node> candidates,
 List<Node> excluded)

Recursive helper method to do the above.

Parameters:

results - result list. Passed between recursive calls to create output

clique - the current Clique being constructed; Graph r in Wikipedia link

candidates - the candidate Nodes for the Clique; Graph p in Wikipedia link

excluded - the Nodes to be excluded from the Clique; Graph x in Wikipedia link

addEdgesInParititeSet

private void addEdgesInParititeSet(Graph graph,
 List<Node> list)

Adds edges to a Graph between all Nodes in a partite set. Remove these edges later with removeEdgesInPartiteSet(edu.claflin.finder.logic.Graph,java.util.List<edu.claflin.finder.logic.Node>).

Parameters:

graph - the Graph to add the Edges to

list - the partite set

removeEdgesInPartiteSet

private void removeEdgesInPartiteSet(Graph graph,
 List<Node> list)

Removes edges in a Graph between all Nodes in a partite set.

Parameters:

graph - the Graph to remove the Edges from

list - the partite set

nameGraphs

private List<Graph> nameGraphs(List<Graph> graphs,
 String originalName,
 boolean bipartite)